A Bit-Parallel Russian Dolls Search for a Maximum Cardinality Clique in a Graph

摘要

Finding the clique of maximum cardinality in an arbitrary graph is an NP-Hardproblem that has many applications, which has motivated studies to solve itexactly despite its difficulty. The great majority of algorithms proposed inthe literature are based on the Branch and Bound method. In this paper, wepropose an exact algorithm for the maximum clique problem based on the RussianDolls Search method. When compared to Branch and Bound, the main difference ofthe Russian Dolls method is that the nodes of its search tree correspond todecision subproblems, instead of the optimization subproblems of the Branch andBound method. In comparison to a first implementation of this Russian Dollsmethod from the literature, several improvements are presented. Some of themare adaptations of techniques already employed successfully in Branch and Boundalgorithms, like the use of approximate coloring for pruning purposes andbit-parallel operations. Two different coloring heuristics are tested: thestandard greedy and the greedy with recoloring. Other improvements are directlyrelated to the Russian Dolls scheme: the adoption of recursive calls where eachsubproblem (doll) is solved itself via the same principles than the RussianDolls Search and the application of an elimination rule allowing not togenerate a significant number of dolls. Results of computational experimentsshow that the algorithm outperforms the best exact combinatorial algorithms inthe literature for the great majority of the dense graphs tested, being morethan twice faster in several cases.